public class Practice1 {
    //https://leetcode.cn/problems/couples-holding-hands/
    //并查集-情侣牵手
    public int MAX = 31;
    public int[] farther = new int[MAX];
    int size;
    public void build(int n){
        for(int i = 0;i <= n;i++){
            farther[i] = i;
        }
        size = n;
    }

    public int find(int n){
        if(farther[n] != n){
            farther[n] = find(farther[n]);
        }
        return farther[n];
    }
    public boolean isSameSet(int a, int b){
        return find(a) == find(b);
    }
    public void union(int a,int b){
        farther[find(a)] = farther[find(b)];
    }
    public int minSwapsCouples(int[] row) {
        build(row.length / 2);
        for(int i = 0;i < row.length;i+=2){
            if(!isSameSet(row[i] / 2,row[i + 1] / 2)){
                union(row[i] / 2,row[i + 1] / 2);
                size--;
            }
        }
        return row.length / 2 - size;
    }
}
